# Stackless Scala

Перевод статьи Runar Oli Bjarnason ["Stackless Scala With Free Monads"][Trampolines] с небольшими отступлениями.


## Для понимания

Исключение абстрактного хвостового вызова (Tail call elimination - TCE) в компиляторе Scala
ограничено саморекурсивными методами, но в остальном хвостовые вызовы не исключаются.
Это делает функции, состоящие из множества более мелких функций, склонными к переполнению стека.
Наличие общего механизма TCE было бы большим преимуществом в Scala,
особенно для функционального программирования.
Трамплининг — популярный метод, который можно использовать для TCE в языках,
изначально его не поддерживающих.
В этой статье дается введение в "батуты" в Scala и расширяется это решение,
позволяющее устранить любой вызов метода, даже вызов, который вообще не находится в хвостовой позиции.
Это полностью исключает использование стека вызовов в программах Scala.


## 1. Введение

Поскольку стек вызовов является ограниченным ресурсом виртуальной машины,
большинство программистов, имеющих некоторый опыт работы со Scala, сталкивались с проблемой,
когда кажущаяся разумной функция выходила за пределы стека
и приводила к сбою программы с ошибкой `StackOverflowError`.
В качестве практического примера рассмотрим обход списка с сохранением некоторого состояния.
Мы будем использовать тип данных `State`, который представляет собой функцию перехода в простом автомате состояний.

```dotty
case class State[S, +A](runS: S => (A, S)):
  def map[B](f: A => B): State[S, B] =
    State[S, B] { s =>
      val (a, s1) = runS(s)
      (f(a), s1)
    }

  def flatMap[B](f: A => State[S, B]): State[S, B] =
    State[S, B] { s =>
      val (a, s1) = runS(s)
      f(a).runS(s1)
    }
```

Функция `runS` принимает некоторое входящее состояние типа `S` и выводит значение типа `A` вместе с новым состоянием. 
Методы `map` и `flatMap` позволяют нам передавать состояние через for-comprehension, 
чтобы писать кажущиеся императивными программы, использующие комбинаторы `State`, такие как:

```dotty
def getState[S]: State[S, S] =
  State(s => (s, s))

def setState[S](s: S): State[S, Unit] =
  State(_ => ((), s))

def pureState[S, A](a: A): State[S, A] =
  State(s => (a, s))
```

Обратите внимание, что `pureState` и `flatMap` вместе [составляют `State` монаду][Category Theory].

В качестве простой демонстрации давайте напишем функцию, которая использует `State` для нумерации всех элементов в списке. 
Не потому, что это убедительный пример использования `State`, а потому, что он прост и демонстрирует переполнение стека.

```dotty
def zipIndex[A](as: List[A]): List[(Int, A)] =
  as.foldLeft(pureState[Int, List[(Int, A)]](List())) { (acc, a) =>
    for {
      xs <- acc
      n  <- getState
      _  <- setState(n + 1)
    } yield (n, a) :: xs
  }.runS(0)
    ._1
    .reverse
```

```dotty
@main def runStateZipIndex(): Unit =
  import State.*
  val list = zipIndex[String](List.fill(10000)("el"))
  println("zipped list = " + list) // java.lang.StackOverflowError
```

Мы используем fold left, чтобы подчеркнуть, что обход списка является хвостовой рекурсией.
Fold создает действие состояния, которое начинается с пустого списка 
и добавляет последовательные элементы в начало, переворачивая исходный список. 
Состояние — это целое число, которое на каждом шаге увеличивается, 
и всё действие составного состояния запускается, начиная с нуля, прежде чем вернуть перевернутый результат.

Но при вызове `zipIndex` в `State.flatMap` происходит сбой со `StackOverflowError`, 
если количество элементов в списке превышает размер стека вызовов виртуальной машины. 
Причина в том, что само действие состояния представляет собой функцию, 
состоящую из нескольких меньших функций, пропорциональных длине списка. 
Несмотря на то, что мы представляем это как последовательность дискретных шагов, 
каждый шаг вызывает следующий шаг способом, который компилятор не может оптимизировать.

Казалось бы, это серьезно ограничивает полезность функционального программирования в Scala. 
В данной статье исследуется пространство решений этой проблемы:

- В разделе 3 мы обсудим известную технику "прыжков на батуте" (trampolining). 
  В trampolining программе вместо того, чтобы каждый шаг вызывал следующий, 
  функции передают следующий шаг одному циклу управления, известному как "батут" (trampoline). 
  Это позволяет нам программно обменивать стек на кучу.
- Затем мы расширим эту технику, добавив операционную монаду (раздел 4), 
  позволяющую превратить любой вызов в хвостовой вызов, который впоследствии может быть устранен. 
  Это будет основным вкладом этой статьи.
- В реализации этой монады есть одна тонкая деталь: если она реализована неправильно, 
  в некоторых случаях она продолжит переполнять стек. 
  В разделе 4.3 мы рассмотрим, что это за случаи и как их обезвредить.
- Программы-"батуты" можно чередовать, обеспечивая модель совместных сопрограмм. Это будет рассмотрено в разделе 5.
- В разделе 6 мы обобщаем trampoline-ы до free monad - чрезвычайно универсальную рекурсивную структуру данных. 
  Мы рассмотрим некоторые функции, работающие со всеми такими структурами (6.1), 
  и обнаружим, что проделанная для trampoline-ов работа, дает те же преимущества для всех free monad.


## 2. Предыстория: устранение хвостовых вызовов в Scala

Компилятор Scala может оптимизировать определенный вид хвостового вызова, известный как саморекурсивный вызов. 
Например, следующее определение сворачивания списка влево оптимизировано компилятором 
для использования постоянного объема стекового пространства:

```dotty
def foldl[A, B](as: List[A], b: B, f: (B, A) => B): B =
  as match
    case Nil     => b
    case x :: xs => foldl(xs, f(b, x), f)
```

Когда компилятор обнаруживает, что метод вызывает себя в хвостовой позиции, 
и если этот метод не может быть переопределен (например, из-за того, что он объявлен private или final), 
рекурсивный вызов метода заменяется простым переходом в скомпилированном коде. 
Это эквивалентно переписыванию хвостовой рекурсии в виде цикла:

```dotty
def foldl[A, B](as: List[A], b: B, f: (B, A) => B): B =
  var z  = b
  var az = as
  while (true)
    az match
      case Nil => return z
      case x :: xs =>
        z = f(z, x)
        az = xs
  z
```

Этот тип оптимизации имеет два преимущества: переход намного быстрее, чем вызов метода, и он не требует места в стеке.

Но в то время как оптимизировать саморекурсивные вызовы легко, 
замена хвостовых вызовов переходами в целом является более сложной задачей. 
В настоящее время (статья написана в 2012) виртуальная машина Java (JVM) допускает только локальные переходы, 
поэтому нет возможности напрямую реализовать хвостовой вызов другого метода в качестве перехода. 
Например, эта взаимная рекурсия не может быть оптимизирована компилятором, 
даже если вызовы находятся в хвостовой позиции:

```dotty
def even[A](ns: List[A]): Boolean =
  ns match
    case Nil     => true
    case _ :: xs => odd(xs)

def odd[A](ns: List[A]): Boolean =
  ns match
    case Nil     => false
    case _ :: xs => even(xs)
```

Эти функции переполнят стек вызовов, если размер `List` больше размера стека.

Хотя будущая JVM может реализовать явную поддержку хвостовых вызовов в байт-коде, 
это не лишено препятствий и может быть не так полезно, как кажется. 
Например, модель выполнения JVM требует, чтобы состояние каждого потока выполнения сохранялось в стеке потока. 
Кроме того, обработка исключений реализуется путем передачи исключения вверх по стеку вызовов 
и JVM предоставляет стек программисту для проверки. 
Фактически, его модель безопасности реализуется путем просмотра разрешений, 
предоставляемых каждому фрейму стека в отдельности. 
Это, в сочетании с созданием подклассов, динамической диспетчеризацией и своевременной компиляцией, 
делает оптимизацию хвостовых вызовов в самом компиляторе Scala трудной для реализации.

К счастью, мы можем обойти все эти проблемы. 
Существует способ, которым можно механически заменить стек на кучу, используя простую структуру данных.


## 3. Батуты: обмен стека на кучу

Мы начнем с очень простого типа данных `Trampoline`. 
Он идентичен по духу, но отличается по реализации от [scala.util.control.TailCalls.TailRec][API].

```dotty
sealed trait Trampoline[+A]: 
  self =>
  
  @annotation.tailrec
  final def runT: A =
    self match 
      case More(k) => k().runT
      case Done(v) => v

case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]
case class Done[+A](result: A)              extends Trampoline[A]
```

`Trampoline` представляет собой пошаговое вычисление, и каждый шаг может иметь только одну из двух форм. 
Шаг `Done(v)` возвращает значение `v`, и в этом случае больше шагов нет. 
У шага `More(k)` больше работы: `k` — это замыкание, которое выполняет некоторую работу и возвращает следующий шаг. 
Метод `runT` — это простой метод хвостовой рекурсии, который выполняет все шаги. 
Он объявлен `final`, чтобы Scala могла исключить хвостовой вызов.

Это решает проблему взаимной рекурсии, показанную ранее. 
Все, что нужно сделать, это механически заменить любой возвращаемый тип `T` на `Trampoline[T]`. 
Вот `odd` и `even`, измененные таким образом:

```dotty
def even[A](ns: List[A]): Trampoline[Boolean] =
  ns match
    case Nil     => Done(true)
    case _ :: xs => More(() => odd(xs))

def odd[A](ns: List[A]): Trampoline[Boolean] =
  ns match
    case Nil     => Done(false)
    case _ :: xs => More(() => even(xs))
```

Вместо прямой рекурсии функции теперь возвращают следующий шаг в виде `Trampoline`, 
который можно выполнить рекурсивно, вызвав метод `runT`. 
Стек больше не переполняется, независимо от того, насколько велики списки аргументов.

```dotty
val list = List.fill(100000)(0)
even(list).runT
// true
```

## 4. Превращение каждого вызова в хвостовой вызов

Давайте посмотрим, сможем ли мы применить решение `Trampoline` к проблеме обхода списка со `State`. 
Нам нужно изменить запуск состояния `State`, 
чтобы вернуть `Trampoline`, который мы можем запускать хвостовой рекурсией:

```dotty
case class State[S, +A](runS: S => Trampoline[(A, S)])
```

Как теперь реализовать метод `flatMap` для составления действий `State`? 
Мы могли бы попробовать так:

```dotty
case class State[S, +A](runS: S => Trampoline[(A, S)]):
  def flatMap[B](f: A => State[S, B]): State[S, B] =
    State[S, B] { s =>
      More { () =>
        val (a, s1) = runS(s).runT
        More(() => f(a) runS s1)
      }
    }
```

Но этого оказывается недостаточно. 
Пример `zipIndex` из раздела 1 по-прежнему будет переполнять стек для больших списков, на этот раз для еще меньших списков. 
Проблема в том, что вызов `runT` находится не в хвостовой позиции, 
поэтому его нельзя оптимизировать или обернуть в `Trampoline`.

### 4.1 Trampoline monad?

Попытаемся решить эту проблему, сделав `Trampoline` монадическим. 
У него уже есть монадический модуль `unit`, который является конструктором `Done` 
(`unit` для монады `M` является функция типа `A => M[A]` для всех `A`. 
Это `unit` в том смысле, что передача его в `flatMap` является тождеством: `fa.flatMap(unit) == fa`). 
Все, что ему нужно, это monadic bind, то есть `flatMap`. 
Давайте добавим метод `flatMap` непосредственно в `Trampoline`, 
чтобы можно было сделать следующее в `State.flatMap`:

```dotty
def flatMap[B](f: A => State[S, B]): State[S, B] =
  State[S, B] { s =>
    More { () =>
      runS(s).flatMap { (a, s1) => More(() => f(a).runS(s1)) }
    }
  }
```

Это определенное улучшение. 
Проблема переносится на метод `flatMap` для `Trampoline`, 
который может возникнуть соблазн реализовать следующим образом:

```dotty
def flatMap[B](f: A => Trampoline[B]): More[B] =
  More[B](() => f(runT))
```

Но это не то, чего мы хотим. Вызов `runT` здесь тоже не в хвосте. 
Кажется, что что бы мы ни пытались сделать, просто невозможно реализовать метод `flatMap` для `Trampoline`, 
не требующий никакого дополнительного стека.

### 4.2 Корректное построение монады

Способ обойти это ограничение — добавить конструктор к типу данных `Trampoline`, 
изменив `flatMap` с вызова метода на вызов конструктора:

```dotty
case class FlatMap[A, +B](sub: Trampoline[A], k: A => Trampoline[B])
    extends Trampoline[B]
```

Батут (trampoline) этой формы можно рассматривать как вызов подпрограммы, 
результат которой возвращается в `k`.

Метод `runT` трейта `Trampoline` теперь должен учитывать этот новый конструктор. 
Для упрощения давайте отделим задачу перехода к следующему шагу от задачи выполнения всех шагов:

```dotty
@annotation.tailrec
final def resume: Either[() => Trampoline[A], A] =
  self match
    case Done(v) => Right(v)
    case More(k) => Left(k)
    case FlatMap(a, f) =>
      a match
        case Done(v) => f(v).resume
        case More(k) => Left(() => FlatMap(k(), f))
        case FlatMap(b, g) =>
          FlatMap(b, x => FlatMap(g(x), f)).resume

@annotation.tailrec
final def runT: A =
  resume match
    case Right(a) => a
    case Left(k)  => k().runT
```

Метод `resume` выполняется путем сопоставления шаблонов на `Trampoline`, 
возвращая либо результат (`Right`), либо следующий шаг в виде `Function0` (`Left`).
То, как мы здесь обрабатываем случай `FlatMap(a,f)` очень важен. 
Мы сопоставляем вызов подпрограммы `a`, и если это `Done`, то просто запускаем продолжение. 
Если же обернут конструктором `More`, то продвинемся на один шаг и обернем `FlatMap` поверх него. 
Если сам вызов подпрограммы содержит вызов подпрограммы, 
у нас есть левоассоциированное вложение `FlatMap`-ов в таком выражении: `FlatMap(FlatMap(b, g), f)`

Крайне важно разрешить этот случай таким образом, чтобы оставаться продуктивным без введения новых stack frames. 
Хитрость заключается в том, чтобы повторно связать справа выражение: `FlatMap(b, x => FlatMap(g(x), f))`.
Когда мы это сделаем, следующая итерация будет соответствовать шаблону `b`, 
и поэтому мы сможем сделать эффективный хвостовой вызов, чтобы снова вызвать `resume`.
Также обратите внимание, что когда мы заглядываем внутрь вложенных конструкторов `FlatMap`, 
то обнаруживаем, что некоторая информация о типе была утеряна. 
В таком шаблоне, как `FlatMap(FlatMap(b, g), f)`, тип `b` не может быть известен, 
поэтому мы должны принять `Any` при построении вложения, ассоциированного справа. 
Это совершенно безопасно, так как можно предположить, 
что левоассоциированное вложение при его построении было хорошо типизировано.
Эта повторная ассоциация использует законы монад. 
`Trampoline` — это монада, а монады по определению ассоциативны. 
Поэтому [правоассоциированные продолжения всегда в точности эквивалентны левоассоциированным](../typeclass/monad/monad.md).

### 4.3 Легкий способ ошибиться

Здесь следует рассмотреть еще один крайний случай. 
Теперь `resume` может переполнить стек, если левая "матрешка" `FlatMap`-ов выше, чем стек вызовов. 
Вызов `f(v)` сделает вызов `g(x)`, который сделает еще один внутренний вызов и т.д. 
Давайте избежим этого, в первую очередь запрещая построение глубоко вложенных левоассоциированных привязок. 
Сделаем конструктор `FlatMap` приватным, открывая вместо него метод `flatMap` в `Trampoline`, 
который перепишем так, чтобы он всегда создавал правоассоциативные привязки:

```dotty
def flatMap[B](f: A => Trampoline[B]): Trampoline[B] =
  self match
    case FlatMap(a, g) => FlatMap(a, x => g(x).flatMap(f))
    case x             => FlatMap(x, f)
```

Чтобы заполнить пробел, мы также должны запретить методу `resume` строить такую "матрешку", 
заменив вызовы конструктора `FlatMap` вызовами метода `flatMap`:

```dotty
case FlatMap(a, f) =>
  a match
    case Done(v) => f(v).resume
    case More(k) => Left(() => k().flatMap(f))
    case FlatMap(b, g) =>
      b.flatMap(x => g(x).flatMap(f)).resume
```

Наконец, для того, чтобы использовать нашу монаду `Trampoline` с for-comprehension Scala, 
нам также нужно реализовать метод `map`, который, конечно же, просто определен в терминах `flatMap`:

```dotty
def map[B](f: A => B): Trampoline[B] =
  flatMap(a => Done(f(a)))
```

### 4.4 Stackless Scala

Предыдущий метод `zipIndex` теперь может выполняться без `StackOverflowError` 
для любого размера входного списка с помощью монады `State`.

Представленный здесь `Trampoline` — это общее решение для устранения stack frame в Scala. 
Теперь мы можем переписать любую программу так, чтобы вообще не использовать пространство стека. 
Рассмотрим программу такого вида:

```dotty
val x = f()
val y = g(x)
h(y)
```

Она может быть легко переписана в следующий вид:

```dotty
for 
  x <- f()
  y <- g(x)
  z <- h(y)
yield z
```

если учесть следующее неявное преобразование:

```dotty
given conv[A]: Conversion[A, Trampoline[A]] with
  def apply(a: A): Trampoline[A] = More(() => Done(a))
```

Единственный тип вызова, для которого ступенчатое преобразование не подходит (и неслучайно), — это саморекурсивный вызов. 
Их легко обнаружить, и в этих случаях мы могли бы вызвать конструктор `More` явно, 
как в этой рекурсивной функции для нахождения n-го числа Фибоначчи:

```dotty
def fib(n: Int): Trampoline[Int] =
  if n <= 1 then Done(n)
  else
    for
      x <- More(() => fib(n - 1))
      y <- More(() => fib(n - 2))
    yield x + y
```

Поскольку это преобразование полностью механическое, мы можем представить, 
что можно было бы написать подключаемый модуль компилятора 
или иным образом расширить компилятор Scala для преобразования всех программ таким образом.


## 5. Совместная многозадачность

Мы видели, как можно последовательно составлять вычисления `Trampoline` с помощью `flatMap`. 
Но также возможно составить их параллельно путем чередования вычислений:

```dotty
infix def zip[B](b: Trampoline[B]): Trampoline[(A, B)] =
  (self.resume, b.resume) match
    case (Right(a), Right(b)) =>
      Done((a, b))
    case (Left(a), Left(b)) =>
      More(() => a() zip b())
    case (Left(a), Right(b)) =>
      More(() => a() zip Done(b))
    case (Right(a), Left(b)) =>
      More(() => Done(a) zip b())
```

Чтобы увидеть всё это в действии, можно ввести побочные эффекты для вывода на консоль:

```dotty
val hello: Trampoline[Unit] =
  for
    _ <- print(" Hello , ")
    _ <- println(" World !")
  yield ()
```

Можно увидеть, что произойдет, если вычисление `hello` чередуется с самим собой:

```dotty
(hello zip hello).runT
// Hello ,  Hello ,  World !
// World !
```

Хотя это параллелизм с одним потоком, легко представить распределение работы между многими потоками. 
Для набора выполняемых батутов любой батут, который не находится в состоянии `Done`, 
может быть возобновлен любым доступным потоком.

Оказывается, этот метод можно обобщить на модель полных симметричных сопрограмм. 


## 6. Свободные монады: обобщение батута

Мы можем думать о `Trampoline` как о сопрограмме, которая может быть приостановлена в `Function0`, а затем возобновлена. 
Но это не единственный конструктор типа, который мы могли бы использовать для приостановки. 
Если абстрагироваться от конструктора типа, то получим следующий тип данных:

```dotty
sealed trait Free[S[+_], A]

object Free:
  private infix case class FlatMap[S[+_], A, B](
      a: Free[S, A],
      f: A => Free[S, B]
  ) extends Free[S, B]

case class Done[S[+_], A](a: A)             extends Free[S, A]
case class More[S[+_], A](k: S[Free[S, A]]) extends Free[S, A]
```

Теперь `Trampoline` может быть определен как:

```dotty
type Trampoline[A] = Free[Function0, A]
```

Как видно из приведенных выше конструкторов данных `Done` и `FlatMap`, 
`Free[S,A]` является монадой для любого ковариантного функтора `S`. 
С точки зрения теории категорий это в точности [свободная монада (Free Monad), порожденная функтором `S`](../typeclass/monad/free-monads.md).

Когда мы говорим, что `S` должен быть функтором, то имеем в виду, что должен существовать экземпляр `Functor[S]`:

```dotty
trait Functor[F[_]]:
  def map[A, B](fa: F[A])(f: A => B): F[B]
```

Для `Function0` функтор определяется просто:

```dotty
given Functor[Function0] with
  def map[A, B](a: () => A)(f: A => B): () => B = () => f(a())
```

### 6.1 Функции, определенные для всех свободных монад

Чтобы конкретизировать утверждение о том, что все свободные монады могут извлечь выгоду из уже проделанной выше работы, 
мы можем обобщить методы, определенные ранее для `Trampoline`. 
Например, вот общая форма `resume`:

```dotty
final def resume(using S: Functor[S]): Either[S[Free[S, A]], A] =
  this match
    case Done(a) => Right(a)
    case More(k) => Left(k)
    case a FlatMap f =>
      a match
        case Done(a)     => f(a).resume
        case More(k)     => Left(S.map(k)(_ flatMap f))
        case b FlatMap g => b.flatMap(x => g(x).flatMap(f)).resume
```

Обратите внимание, что по существу это определение точно такое же, как и для `Trampoline`. 
Единственными отличиями являются сигнатура типа, дополнительный неявный аргумент `Functor` 
и тот факт, что мы заменили явную конструкцию `Function0` вызовами `map` для нашего функтора. 
Это также верно для обобщенных реализаций `zip`, `map` и `flatMap`. 
Вот `zip`:

```dotty
infix def zip[B](b: Free[S, B])(using S: Functor[S]): Free[S, (A, B)] =
  (resume, b.resume) match
    case (Left(a), Left(b)) =>
      More(S.map(a)(x => More(S.map(b)(y => x zip y))))
    case (Left(a), Right(b)) =>
      More(S.map(a)(x => x zip Done(b)))
    case (Right(a), Left(b)) =>
      More(S.map(b)(y => Done(a) zip y))
    case (Right(a), Right(b)) =>
      Done((a, b))
```

### 6.2 Общие типы данных как свободные монады

Неформально мы можем рассматривать `Free[S, A]` как тип любого вычисления, 
которое может разветвляться по некоторому функтору `S` и заканчиваться некоторыми данными типа `A` на концах. 
Чтобы понять это, рассмотрим обычное бинарное дерево решений. 
Это свободная монада, функтор которой «разбивает» вычисление на две части в каждой ветви:

```dotty
type Pair[+A]    = (A, A)
type BinTree[+A] = Free[Pair, A]
```

Случай `Done` для `BinTree[A]` — это лист, которая содержит значение типа `A`, 
а случай `More` — это ветвь, содержащая два значения типа `BinTree[A]`. 
Наша свободная монада (в случае с `FlatMap`) позволяет взять каждый лист дерева, 
применить к нему функцию создания дерева и привить полученное дерево вместо этого листа. 
И поскольку это экземпляр `Free`, работа, которую мы уже проделали над `Trampoline`, 
позволяет делать это за постоянное время и с постоянным пространством стека.

Чтобы получить дерево с любым количеством возможных ветвей в каждом узле вместо двух, 
мы должны разветвляться с помощью функтора `List`:

```dotty
type Tree[+A] = Free[List, A]
```

Действительно, сам `List` может быть выражен как приложение `Free`:

```dotty
type List[A] = Free[[X] =>> (A, X), Unit]
```

В этом представлении `List[A]` — это сопрограмма, 
которая создает значение типа `A` при каждом возобновлении работы или `Unit`, если это пустой список. 
Действие свободной монады здесь — это не действие «монады списка» как таковой 
(чье монадическое связывание заменяет каждый элемент списка новым списком), 
а монады, которая позволяет нам присоединять один список к другому. 
Опять же, поскольку это приложение `Free`, 
мы можем выполнять эту операцию за постоянное время и с постоянной памятью.

### 6.3 Свободная монада для State

Хотя примеры свободных монад, представленные здесь, очень просты, 
приостановочный функтор для свободной монады может быть произвольной сложности. 
Он может производить выходные данные и ожидать входные данные в любой мыслимой комбинации. 
Мы могли бы, например, смоделировать `State` как небольшой язык, где мы можем получить и установить состояние:

```dotty
sealed trait StateF[S, +A]
case class Get[S, A](f: S => A)  extends StateF[S, A]
case class Put[S, A](s: S, a: A) extends StateF[S, A]
```

В конструкторе `Get` `f` — это функция, которая ожидает на вход текущее значение состояния. 
В конструкторе `Put` `s` — это новое состояние, 
а `a` — остальная часть вычислений (которые предположительно могут что-то сделать с этим состоянием).
Нам понадобятся доказательства того, что наш тип данных на самом деле является функтором:

```dotty
given statefFun[S]: Functor[[X] =>> StateF[S, X]] = new:
  def map[A, B](m: StateF[S, A])(f: A => B): StateF[S, B] =
    m match
      case Get(g)    => Get(s => f(g(s)))
      case Put(s, a) => Put(s, f(a))
```

Затем мы можем закодировать монаду, подобную `State`, 
непосредственно как свободную монаду, сгенерированную нашим функтором `StateF`:

```dotty
type FreeState[S, A] = Free[[X] =>> StateF[S, X], A]
```

Комбинатор `pureState` из раздела 1 поставляется "бесплатно" с конструктором `Done` нашей свободной монады.

```dotty
def pureState[S, A](a: A): FreeState[S, A] = Done(a)
```

А два других, для получения и установки состояния, легко определить:

```dotty
def getState[S]: FreeState[S, S] = More(Get(s => Done(s)))

def setState[S](s: S): FreeState[S, Unit] = More(Put(s, Done(())))
```

Для запуска действия с заданным начальным состоянием используется простой цикл:

```dotty
def evalS[S, A](s: S, t: FreeState[S, A]): A =
  t.resume match
    case Left(Get(f))    => evalS(s, f(s))
    case Left(Put(n, a)) => evalS(n, a)
    case Right(a)        => a
```

Теперь мы можем писать чистые функции, сохраняющие некоторое состояние в этой монаде. 
Например, вот `zipIndex` из раздела 1, на этот раз с использованием нашей монады `FreeState`:

```dotty
def zipIndex[A](as: List[A]): List[(Int, A)] =
  evalS(
    0,
    as.foldLeft(pureState[Int, List[(Int, A)]](List())) { (acc, a) =>
      for
        xs <- acc
        n  <- getState
        _  <- setState(n + 1)
      yield (n, a) :: xs
    }
  ).reverse
```

Реализация почти идентична, и она работает в постоянном стеке без необходимости проходить через `Trampoline`. 
Вывод состоит в том, что не всегда необходимо или желательно изменять существующую структуру данных. 
Мы можем изобретать новые свободные монады собственного дизайна a la carte (см. 7.4) и пожинать те же плоды.


## 7. Существующая работа

Ничто из представленного здесь не является особенно оригинальным, хотя части взяты из разных источников 
и, насколько мне известно, ранее не собирались таким образом, особенно в Scala (2012 год - на момент написания статьи).

### 7.1 Батуты

Использование "батутных" функций для реализации хвостовых вызовов в языках, ориентированных на стек, — 
[хорошо известная техника][Trampolined Style], реализованная во многих языках в виде библиотек или компиляторов.

Стандартная библиотека Scala (в версии `3.2.2`) включает объект [TailCalls][API], 
предоставляющий структуру данных `TailRec`.

### 7.2 Операционные монады

Реализация свободных монад в этой статье имеет монадическую привязку, 
конкретизированную на куче как конструкторе данных, а не на вызове метода в стеке. 
Это позволило манипулировать привязками как данными и выполнять повторную ассоциацию. 
Можно назвать эту технику использованием операционной монады, основанной на работе [Heinrich Apfelmus][Apfelmus]. 
Он обсуждает монады, представляющие программы с явно овеществленным стеком, 
но не свободные монады или трамплины, представленные здесь.

Наша монада `FreeState` также является операционной монадой, явно овеществляющей две операции `Get` и `Put`.

### 7.3 Свободные монады и сопрограммы

Идея обобщения батутов пришла из _Coroutine Pipelines_ Блажевича в октябрьском выпуске ["The Monad Reader" за 2011 год][The monad reader]. 
Хотя он не делает явных ссылок на свободные структуры, ясно, 
что его тип `Coroutine` является преобразованием Free monad. 
В текущей реализации на Scala необходимо отказаться от параметризации дополнительной монады, 
чтобы сохранить удаление хвостовых вызовов. 
Вместо того, чтобы быть написанным как монадный преобразователь, 
`Free` может быть преобразован монадным преобразователем для того же эффекта. 
Например, `Coroutine[A, [X] =>> State[S, X], B]` становится `StateT[S, [X] =>> Free[A, X], B]`, 
учитывая: `case class StateT[S, M[_], A](run: S => M[(A, S)])`

Обсуждение Блажевича гораздо более подробно описывает 
"виды взаимодействующих сопрограмм, которые могут быть выражены как свободные монады 
с производителями, потребителями и преобразователями между ними".

### 7.4 Проблема выражения

Идея монады `FreeState`, моделирующей переходы состояний с помощью побочного продукта `Get` и `Put`, 
взята из статьи Wouter Swierstra 2008 года ["Типы данных на заказ"][Swierstra].
Swierstra использует свободную монаду для создания специальных рекурсивных типов данных 
из побочного произведения произвольных функторов и классов типов Haskell 
для обработки диспетчеризации в различных случаях побочного произведения.

### 7.5 Кодовая плотность

Акт связывания всех монадических связей справа можно понимать 
как [применение кодовой плотности (application of codensity)][Category Theory]. 
Это ключевое понимание пришло из обсуждения с Эдом Кметтом [его работы][Free Monads for Less] 
со структурой данных ввода-вывода, выраженной в виде свободной монады.

Janis Voigtlander обсуждает коденсальность свободных монад в своей статье 
["Асимптотическое улучшение вычислений над свободными монадами"][Asymptotic Improvement of Computations over Free Monads], 
хотя он не называет понятие "коплотность" явным образом. 
Цель его статьи — не экономия места в стеке как такового, а повышение производительности.

Voigtlander объясняет, как спуск в левоассоциированные связывания в свободной монаде 
имеет квадратичные накладные расходы, 
и он продолжает устранять эти накладные расходы, используя монаду кодовой плотности.

### 7.6 Итерации

Безопасный и модульный инкрементный ввод-вывод уже давно недостижим в чисто функциональных языках, таких как Haskell. 
[Олег Киселев][Kiselyov, Incremental] и [Джон Лато][Lato, Iteratee] обсуждают идею итерации, 
чистого автомата, который потребляет входные данные, 
производит эффекты и может поддерживать некоторое внутреннее состояние.

`Iteratees` — это не совсем свободные монады, 
но они представляют собой композицию свободной монады с другим функтором, 
поэтому их можно выразить как приложение `Free`. 
Тип `IterV` в статье Лато можно очень грубо выразить следующим образом:

```dotty
type IterV[I, O] = Free[[X] =>> I => X, (I, O)]
```

Поскольку `IterV` отслеживает оставшуюся часть ввода (во многом как синтаксический анализатор), 
технически он не является свободным. 
Но в статье также обсуждается "внутренний итератор", который они называют enumeratee, 
преобразующий один поток входных данных в поток выходных данных, 
и этот тип проще выразить как свободную монаду:

```dotty
type Enumeratee[I, O, A] = Free[[X] =>> Either[I => X, (O, X)], A]
```

Этот тип сопрограммы представляет собой преобразователь потока, который может либо запрашивать ввод типа `I`, 
либо выдавать вывод типа `O` каждый раз, когда он возобновляет работу, 
и завершается со значением типа `A`.


## 8. Выводы и дальнейшая работа

Мы увидели, как можно использовать трамплины для выполнения рекурсивных вызовов в куче вместо стека в Scala. 
Техника проста, но есть некоторые детали, которые мы должны реализовать определенным образом, 
учитывая возможности и ограничения языка Scala и JVM, иначе решение не будет работать.

Мы увидели, как батуты соотносятся с общей идеей свободных монад над функтором 
и как все наши опасения по поводу батутов, а также все преимущества легко переносятся на любую такую монаду.

Предстоит провести дополнительные исследования, чтобы реализовать эти идеи в компиляторе Scala — 
возможно, в виде подключаемого модуля — 
чтобы включить программирование без стека без каких-либо дополнительных усилий со стороны программиста.

Свободные монады имеют гораздо больше применений, чем мы здесь себе представляли. 
С ростом давления в промышленности на чистое функциональное программирование 
возникает потребность в модели программирования, которая позволяет составлять модульные вычисления, 
эффективные с точки зрения времени и памяти. 
Многообещающая работа ведется над итерациями и монадическими потоками, 
но в Scala пока нет очень чистого API для них. 
Возможно, библиотека, основанная на свободных монадах, могла бы все изменить.


---

**Ссылки:**

- [Исходный код](https://gitverse.ru/artemkorsakov/scalabook/content/master/examples/src/main/scala/ru/scalabook/fp/trampolining)
- [Эффекты, трамплины и зачем нам это надо - Алексей Шуксто, Scala Meetup 20.04.23](https://www.youtube.com/watch?v=4jSi6RRIaCk)
- [Asymptotic Improvement of Computations over Free Monads - Janis Voigtlander][Asymptotic Improvement of Computations over Free Monads]
- [Category Theory - S. Awodey][Category Theory]
- [Data types a la carte - Wouter Swierstra][Swierstra]
- [Free Monads for Less - E. A. Kmett][Free Monads for Less]
- [Functional Programming in Scala, Second Edition, Chapter 13](https://www.manning.com/books/functional-programming-in-scala-second-edition?query=Functional%20Programming%20in%20Scala,%20Second%20Edition)
- [Incremental multi-level input processing and collection enumeration - O. Kiselyov][Kiselyov, Incremental]
- [Iteratee: Teaching an Old Fold New Tricks - J. W. Lato][Lato, Iteratee]
- [Scala API][API]
- [Stackless Scala With Free Monads - Runar Oli Bjarnason][Trampolines]
- [Stackless Scala with Free Monads - hearding cats](http://eed3si9n.com/herding-cats/stackless-scala-with-free-monads.html)
- [Stackless Scala with Free Monads - learning ScalaZ](http://eed3si9n.com/learning-scalaz/Stackless+Scala+with+Free+Monads.html)
- [The Monad.Reader Issue 19][The monad reader]
- [The Operational Monad Tutorial - Heinrich Apfelmus][Apfelmus]
- [Trampolined Style - Steven E. Ganz and Daniel P. Friedman and Mitchell Wand][Trampolined Style]

[API]: https://www.scala-lang.org/api/3.2.2/scala/util/control/TailCalls$.html
[Apfelmus]: https://apfelmus.nfshost.com/articles/operational-monad.html
[Asymptotic Improvement of Computations over Free Monads]: https://janis-voigtlaender.eu/papers/AsymptoticImprovementOfComputationsOverFreeMonads.pdf
[Category Theory]: https://books.google.ru/books/about/Category_Theory.html?hl=ru&id=AIhUtQAACAAJ&redir_esc=y
[Kiselyov, Incremental]: https://okmij.org/ftp/Streams.html
[Lato, Iteratee]: https://themonadreader.files.wordpress.com/2010/05/issue16.pdf
[Free Monads for Less]: http://comonad.com/reader/2011/free-monads-for-less/
[Swierstra]: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.4131&rep=rep1&type=pdf
[The monad reader]: https://themonadreader.files.wordpress.com/2011/10/issue19.pdf
[Trampolined Style]: https://dl.acm.org/doi/abs/10.1145/317636.317779
[Trampolines]: https://blog.higher-order.com/assets/trampolines.pdf



